#include <iostream>
#include <vector>
using namespace std;
template <typename T>
void bubble_sort(T arr[], int len)
{
    int i, j;
    for (i = 0; i < len - 1; i++)
    {
        for (j = 0; j < len - 1 - i; j++)
        {
            // 最大的挪到最右边
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}
template <typename T>
void selection_sort(vector<T> &arr)
{
    for (int i = 0; i < arr.size() - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[min] > arr[j])
                min = j;
        }
        swap(arr[min], arr[i]);
    }
}
template <typename T>
void insertion_sort(vector<T> &arr)
{
    for (int i = 1; i < arr.size(); i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (key < arr[j] && j >= 0)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
template <typename T>
void shell_sort(vector<T> &arr)
{
    int n = arr.size();
    // 对每组间隔为h的分组进行排序，刚开始 h = n / 2，h = 1 时退化成简单插入排序
    for (int h = n / 2; h > 0; h /= 2)
    {
        for (int i = h; i < n; i++)
        {
            insert_h(arr, h, i);
        }
    }
}
template <typename T>
void insert_h(vector<T> arr, int h, int i)
{
    // 将arr[i]插入到所在分组的正确位置上(arr[i-2*h],arr[i-h]...)
    int temp = arr[i];
    int j = i - h;
    while (temp < arr[j] && j >= 0)
    {
        arr[j + h] = arr[j];
        j = j - h;
    }
    arr[j + h] = temp;
}

void MergeSort(vector<int> &arr)
{
    // 非递归,自底向上的归并排序
    int n = arr.size();
    for (int size = 1; size < n; size += size)
    {
        for (int left = 0; left < n - size; left += size + size)
        {
            merge(arr, left, left + size - 1, min(left + size + size - 1, n - 1));
        }
    }
}

void merge(vector<int> &arr, int left, int mid, int right)
{
    vector<int> temp;
    for (int i = left; i <= right; ++i)
        temp[i] = arr[i];
    int i = left, j = mid + 1, index = left;
    while (i <= mid && j <= right)
    {
        if (temp[i] < temp[j])
            arr[index++] = temp[i++];
        else
            arr[index++] = temp[j++];
    }
    while (i <= mid)
        arr[index++] = temp[i++];
    while (j <= right)
        arr[index++] = temp[j++];
}

void QuickSort(vector<int> &arr, int begin, int end)
{
    /* 快速排序
     *  1. 选定pivot
     *  2. 将大于pivot的数字放在pivot的右边
     *  3. 将小于pivot的数字放在pivot的左边
     *  4. 分别对左右子序列重复前3步操作
     */
    if (begin >= end)
        return;
    int i = partition(arr, begin, end);
    QuickSort(arr, begin, i - 1);
    QuickSort(arr, i + 1, end);
}

int partition(vector<int> &arr, int l, int r)
{
    int i = l, j = r;
    int pivot = arr[l]; // 优化：随机选择基准数pivot
    while (i < j)
    {
        while (arr[j] >= pivot && i < j)
            j--;
        while (arr[i] <= pivot && i < j)
            i++;
        swap(arr[i], arr[j]);
    }
    swap(pivot, arr[i]);
    return i;
}

/* 堆排序
 *  1. 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子节点数值大）
 *  2. 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆
 */
void HeapAdjust(vector<int> &arr, int parent, int length)
{
    int temp = arr[parent];     // temp保存当前父节点
    int child = 2 * parent + 1; // 先取左孩子
    while (child < length)
    {
        // 如果有右孩子结点，并且右孩子结点的值>左孩子结点，则选取右孩子结点
        if (child + 1 < length && arr[child] < arr[child + 1])
        {
            child++;
        }
        if (temp >= arr[child])
        {
            break;
        }
        arr[parent] = arr[child];
        // 继续向下筛选
        parent = child;
        child = 2 * parent + 1;
    }
    arr[parent] = temp;
}

void HeapSort(vector<int> &arr)
{
    int length = arr.size();
    // 循环建立初始堆,从n-1层开始到顶层
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        HeapAdjust(arr, i, length);
    }
    // n-1次循环，完成排序
    for (int i = length - 1; i > 0; i--)
    {
        // 最后一个元素和第一个元素交换
        swap(arr[i], arr[0]);
        HeapAdjust(arr, 0, i); // 堆长度为i
    }
}
